package leetbook.dynamic_plan;


public class Solution395 {

    public static void main(String[] args) {

        String s = "aaabb";
        System.out.println(new Solution395().longestSubstring(s,3));
    }

    /**
     * 用count记录每个字符出现的次数，斜下更新
     */
    public int longestSubstring1(String s, int k) {
        int[] count = new int[26];
        int res = 0, n = s.length();
        for (int col = 0; col < n; col++) {
            int[] cur = count.clone(); //用于本次[0,col]循环
            //向右下走,[0,col]->[i,j]->[,n-1]
            for ( int i = 0, j = col; j < n; i++, j++) {
                //加入最右字符
                cur[s.charAt(j)-'a']++;
                //统计
                boolean flag = true;
                for (int l = 0; l < 26; l++) {
                    if(cur[l]>0&&cur[l]<k){
                        flag = false;
                        break;
                    }
                }
                if(flag) res = Math.max(res,j-i+1);
                //删除最左字符
                cur[s.charAt(i)-'a']--;
            }
            count[s.charAt(col)-'a']++;//用于下次[0,col+1]循环
        }
        return res;
    }

    /**
     * 分治
     */
    public int longestSubstring(String s, int k) {
        return dfs(s,k,0,s.length()-1);
    }

    /*
     * 优化dfs
     */
    public int dfs(String s, int k, int start, int end) {

        if(end-start+1<k) return 0; //不可能出现符合条件的字符串
        //寻找出现次数小于k的字符下标作为分割
        int[] count = new int[26];
        for (int i = start; i <= end; i++) {
            count[s.charAt(i)-'a']++;
        }
        int split = 0;
        for (int i = 0; i < 26; i++) {
            if(count[i]>0&&count[i]<k){
                split += 'a' + i;
                break;
            }
        }
        //出现字符个数都不小于k
        if(split==0) return end-start+1;
        //有字符出现次数不满足，一次把这些字符分完
        int res = 0, j = start;
        //寻找第一个split
        while (s.charAt(j)!=split) j++;
        res = Math.max(res,dfs(s,k,start,j-1));
        //寻找其他split
        int lastSplit = j;
        while (j<=end){
            while (j<=end&&s.charAt(j)!=split) j++;
            res = Math.max(res,dfs(s,k,lastSplit+1,j-1));
            lastSplit = j++; //j是切分位置，j要增1
        }
        return res;
    }


    public int dfs1(String s, int k, int start, int end) {
        if(end-start+1<k) return 0; //不可能出现符合条件的字符串
        //寻找出现次数小于k的字符下标作为分割
        int[] count = new int[26];
        for (int i = start; i <= end; i++) {
            count[s.charAt(i)-'a']++;
        }
        int split = 0;
        for (int i = 0; i < 26; i++) {
            if(count[i]>0&&count[i]<k){
                split += 'a' + i;
                break;
            }
        }
        //出现字符个数都不小于k
        if(split==0) return end-start+1;
        //有字符
        for (int i = start; i <= end; i++) {
            if(s.charAt(i)==split){
                split = i;
                break;
            }
        }
        return Math.max(dfs(s,k,start,split-1),dfs(s,k,split+1,end));
    }
}
